package vip.liux.backend.infrastructure.algorithm;


import java.util.HashMap;
import java.util.Map;

public class LRU<K, V> {
    // 双向链表节点类
    private class Node {
        K key;
        V value;
        Node prev;
        Node next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    // 存储键到节点的映射
    private final Map<K, Node> cache;
    // 缓存的最大容量
    private final int capacity;
    // 头节点和尾节点
    private Node head, tail;

    public LRU(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
    }

    // 获取缓存中的值
    public V get(K key) {
        Node node = cache.get(key);
        if (node == null) {
            return null;
        }
        // 移动节点到链表头部
        moveToHead(node);
        return node.value;
    }

    // 向缓存中添加键值对
    public void put(K key, V value) {
        Node node = cache.get(key);
        if (node != null) {
            // 如果键已经存在，更新值并移动到链表头部
            node.value = value;
            moveToHead(node);
        } else {
            // 如果键不存在，创建新节点
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addNodeToHead(newNode);
            if (cache.size() > capacity) {
                // 如果缓存已满，移除尾节点
                Node tail = popTail();
                cache.remove(tail.key);
            }
        }
    }

    // 添加节点到链表头部
    private void addNodeToHead(Node node) {
        node.prev = null; // 头节点的前驱节点为空
        node.next = head; // 新节点的后继节点为原头节点
        if (head != null) { // 如果原头节点不为空
            head.prev = node; // 原头节点的前驱节点为新节点
        }
        head = node; // 新节点成为新的头节点
        if (tail == null) { // 如果尾节点为空
            tail = node; // 新节点也成为尾节点
        }
    }

    // 移动节点到链表头部
    private void moveToHead(Node node) {
        removeNode(node); // 从链表中移除节点
        addNodeToHead(node); // 添加节点到链表头部
    }

    // 移除节点
    private void removeNode(Node node) {
        if (node.prev != null) { // 如果前驱节点不为空
            node.prev.next = node.next; // 前驱节点的后继节点指向后继节点
        } else {
            head = node.next; // 前驱节点为空，说明是头节点，更新头节点为后继节点
        }
        if (node.next != null) { // 如果后继节点不为空
            node.next.prev = node.prev; // 后继节点的前驱节点指向前驱节点
        } else {
            tail = node.prev; // 后继节点为空，说明是尾节点，更新尾节点为前驱节点
        }
    }

    // 弹出尾节点
    private Node popTail() {
        Node res = tail;
        removeNode(tail);
        return res;
    }
}